import java.util.Arrays;
import java.util.Stack;

/**
 * 给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，
 * 其中 answer[i] 是指在第 i 天之后，才会有更高的温度。
 * 如果气温在这之后都不会升高，请在该位置用 0 来代替。
 */
public class Test739 {

    public static void main(String[] args) {

        int[] arr = {73,74,75,71,69,72,76,73};
        int[] ret = dailyTemperatures(arr);
        System.out.println(Arrays.toString(ret));
    }
    // 单调栈
    public static int[] dailyTemperatures(int[] temperatures) {
        int[] ret = new int[temperatures.length];
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        for (int i = 1; i < temperatures.length; i++) {
            if (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]){
                while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]){
                    ret[stack.peek()] = i - stack.peek();
                    stack.pop();
                }
                stack.push(i);
            }else if (temperatures[i] <= temperatures[stack.peek()]){
                stack.push(i);
            }
        }
        if (!stack.isEmpty()){
            while (!stack.isEmpty()){
                ret[stack.pop()] = 0;
            }
        }
        return ret;
    }


    // 暴力法：
//    public static int[] dailyTemperatures(int[] temperatures) {
//        int[] ret = new int[temperatures.length];
//        for (int i = 0; i < temperatures.length-1; i++) {
//            int temp = temperatures[i];
//            int index = i;
//            for (int j = i+1; j < temperatures.length; j++) {
//                if (temperatures[j] > temp){
//                    ret[index++] = j-i;
//                    break;
//                }
//            }
//        }
//        return ret;
//    }
}
